1. Field of the Invention
The present invention relates to computer graphics, and more particularly to a geometric preprocessor for Gouraud-shading a spotlight and to the intensity-value smoothing of a scene having a boundary where a difference between intensity-values becomes large, such as the spotlight.
2. Related Art
Many of the graphic accelerators, which is hardware, and the Open GL (trademark of Silicon Graphics Inc.) of a graphic API (application program interface) being now most extensively used provide the Gouraud shading as a rendering function. The Gouraud shading is a shading method where an intensity-value (e.g., an intensity-value including data representative of the strength of each of red, green, and blue) is calculated at each vertex of geometric data (object) and then the intensity-value at each vertex is linearly interpolated, thereby approximating an intensity-value at an arbitrary point in the geometric data. (For a more detailed discussion on the Gouraud shading, see H. Gouraud, "Computer Display of Curved Surfaces," Ph.D. Dissertation, University of Utah, UTEC-CSs-71-113, 1971) Point light sources, parallel light rays, and spotlight are now being standardized as the supported kind of a light source in the graphic API, including the aforementioned Open GL. However, hitherto the spotlight has not been simulated in Gouraud shading, unless it is specially processed.
This results from the fact that, if the vertices of a geometrical figure on which the light from a spotlight source is irradiated are not inside of the cone angle of the spotlight, the intensity-values on the vertices will become zero and the intensity-values interpolated at points in the geometrical figure will also become zero. For instance, consider the situation where a spotlight is hung from the ceiling of a room and rendered by Gouraud shading. When the floor is constructed from a plate, which is flat geometrically, the area which is irradiated by the spotlight is included completely inside of the flat plate. If another light source does not exist, the screen will become black. In order to avoid a phenomenon such as this, there has hitherto been employed a method where original data is suitably meshed into small elements and then Gouraud shading is performed again. However, even if processing such as this were performed, the part illuminated by spotlight would not become a circular arc shape which is the original shape.
Now, the general concept of a spotlight source will be described. The spotlight source is a sort of standard point light source normally supported by many renderers and graphic APIs (e.g., PHIGS+, Open GL, VRML, Renderman) and is limited on the direction of irradiation. More accurately, the spotlight source is a point light source such as irradiating only objects which are contained inside of a cone where the light source is the vertex of the cone and the irradiation direction is the center axis of the cone. In practice, the spotlight generally has such a property that, even when an object is inside of a cone space where the spotlight is irradiated, the intensity-value of irradiated light is attenuated in proportion to an exponent of a cosine of an angle formed with the center axis, as the object or a point in the object goes away from the center of the cone. FIG. 1 shows a schematic view of a spotlight. Excluding color and intensity parameters, the spotlight is represented by five parameters, that is, four parameters shown in the figure and a beam distribution parameter indicating the degree of attenuation when the object or a point in the object goes away from the center axis. That is, the spotlight is expressed by the following parameters:
1. from (start point)
2. to (end point)
3. coneangle (cone angle)
4. conedeltaangle (delta angle)
5. beamdistribution (degree of attenuation)
If, as shown in FIG. 1, it is assumed that the degree of attenuation of spotlight is .alpha., the cone angle is .theta., the delta angle is .delta., the directional vector from a start point to an end point is A, the directional vector from a start point to an arbitrary point inside of the cone angle is L, the spotlight is white, and the intensity is 1, the intensity I at a point w will be given by the following equation. EQU I=x smoothstep (cos .theta., cos (.theta.-.delta.), x) (1)
where x=(L.multidot.A).sup..alpha. and the smoothstep (a, b, c) is given by the following Equation 1.
Equation 1! ##EQU1## In Equation 1, hermite (x)=2x.sup.3 -3x.sup.2 +1. The smoothstep (a, b, x) is shown in FIG. 2.
The delta angle .delta.is used for grading a circular edge which forms the boundary of an area irradiated by the spotlight. In practice, when an angle which a point on the irradiated surface makes with the center axis of the spotlight is between .theta.-.delta. and .theta., the former is taken to be 1.0 and the latter is taken to be 0.0. The intention of the delta angle is to smoothly interpolate the angle between .theta.-.delta. and .theta.. .delta. normally takes a value in the range of 0.ltoreq..delta..ltoreq..theta.. When .theta.=0, the aforementioned function of smoothstep results in a discontinuous normal step function with a=b=cos .theta.. Therefore, a clear boundary is drawn.
The point that the spotlight most differs from other standard light sources (e.g., point light sources and parallel light beams) is that a considerable difference in light and shade occurs in the boundary between a spotlight-irradiated portion and an unirradiated portion, even when there is no screening relationship between an object in space and a given light source. Sometimes, this property of the spotlight is utilized positively. For example, in the case of a renderer which cannot perform a shading process, a plurality of sets of spotlight beams are used to enhance quality. Also, the property of the spotlight is often used for enhancing the rendering process speed which tends to be slow in the case of a plurality of point light sources. However, Phong shading, not Gouraud shading which incidentally is often supported by hardware, is indispensable for accurately expressing the feeling of the spotlight.
The Phong shading is a shading method where, from a normal vector given at each vertex of geometrical data (object), a normal vector at an arbitrary point in the geometrical data is linearly interpolated and, based on the linearly interpolated normal vector, intensity calculation is performed again (B-T. Phong, "Illumination for Computer-Generated Images," Ph.D. Dissertation, University of Utah, UTEC-CSs-73-129, 1973). The Phong shading has the advantage that the local reflection state of illumination, such as highlight, can be modeled with fidelity, but, on the other hand, it has the disadvantage that it is difficult to make with hardware and an intensity-value must be calculated at each vertex and therefore the processing speed is slow.
Thus, an additional method is needed for performing Gouraud shading of the spotlight without damaging the quality. The method which has been most used is to give small meshes in advance, as described above. Even in this case there is the possibility that aliasing will occur near a boundary whose intensity change is large (Aikawa, "Open GL Programming Guide," Gijyutsu Hyoron-sha, Effect of Spotlight, FIGS. 5-13, p. 87, 1995). As another method, "projection texture" is used (M. Segel, et al., "Fast Shadows and Lighting Effects Using Texture Mapping," Proc. SIGGRAPH'92, 249-252, 1992). This method has the characteristic that the spotlight can be simulated at high speeds by using texture mapping without damaging the quality and under hardware support. However, unless a graphic accelerator supporting texture mapping by hardware exists, the aforementioned method is not practical because it requires a large capacity storage and is expensive.
As a similar method, an approach using reflection mapping has been proposed in order to alleviate aliasing caused by a difference in light and shade which occurs due to highlight (D. Voorhies and J. Foran, "Reflection Vector Shading Hardware," Proc. SIGGRAPH'94, 163-166, 1994). This method can satisfactorily cope with aliasing which occurs due to a difference in light and shade around highlight. However, the reflection mapping is realized by originally mapping a hemispherical (or whole spherical) space, such as the celestial sphere, on an object, so the reflection mapping is effective only for an object itself which is spherical in shape. In general, no reflection mapping effects will arise in flat objects. Furthermore, in the case where reflection mapping is performed for all objects in a scene, a large capacity storage area is required and the performance is also reduced extremely.
Published Unexamined Patent Application (PUPA) No. 3-296178 discloses a unit which includes overlap judging means for judging whether or not an irradiated region of each spotlight source and each surface of an output object overlap each other when Gouraud shading is performed, overlap region generating means for obtaining each of the overlapped surfaces of the output object and an overlapped region in the overlapped surfaces, based on a result of the judgment of the overlap judging means, and region segmenting means for segmenting the obtained overlapped region obtained with the overlapped surface into polygons and giving them to intensity calculating means. When the overlapped region is obtained in the aforementioned way, the irradiated region of a spotlight source is normally a circular arc and therefore is expressed with a quadric. With this function and a function expressing an irradiated surface, a crossed line is obtained, so a considerable amount of calculation is required. If an irradiated surface is a quadric, the same amount as an amount of calculation of a function of the degree four will be required and performance will become worse. In addition, the aforementioned publication shows an embodiment where an overlapped surface is detected and then the overlapped surface is segmented into small areas, however, this is an idea which does not differ from the aforementioned method that small meshes are given in advance.
As described above, there is no conventional method which can effectively handle a spotlight source by the Gouraud shading.
Now, a radiosity method will be described from the relation with the present invention.
The radiosity method is one of the rendering methods based on a global illumination model and is a method where the intensity of an object is calculated on the assumption that incident light is perfectly diffused and reflected at all surfaces of the object. FIG. 3 is a diagram showing the geometrical relation between a point X.sub.i on a certain surface A.sub.i and a point X.sub.j on another surface A.sub.j. When the areas of the respective surface elements are sufficiently small in the aforementioned positional relation, the rate of photons emerging from the small surface dA.sub.i and arriving at the small surface dA.sub.j depends upon only the geometrical position relation. This rate is called a form factor (F.sub.ij) and represented by the following Equation 2.
Equation 2! ##EQU2## In Equation 2, r is the distance between the small surfaces dA.sub.i and dA.sub.j and V.sub.ij is a flag which indicates whether dA.sub.j is seen from dA.sub.i. When dA.sub.i is seen, the flag is 1, and when dA.sub.i is not seen, the flag is 0.
In general, the radiosity B.sub.i, emitted from the small surface dAi, is expressed by the following Equation 3 from self-radiation E.sub.i, reflectance factor .rho..sub.i that is the rate at which the radiosity B.sub.j from another small surface (in this embodiment, j=1 through N) is reflected, and form factor F.sub.ij that is the rate at which photons arrive at the small surface dA.sub.i.
Equation 3! ##EQU3##
If Equation 3 is solved for all radiosities Bi, the radiosities for all small surfaces will be obtained. In Equation 3 the self-radiation E.sub.i and the reflectance factor .rho..sub.i (this represents the color of an element to which the beams are emitted.) are set values. Therefore, if the form factors F.sub.ij between all geometrical elements are obtained, the radiosities can be calculated. In FIG. 3, if it is assumed that the surface A.sub.i is a light source, it will be found that a surface light source can be naturally handled in the radiosity method.
However, generally the calculation of the form factor given by Equation 2 cannot be solved analytically. Many of the conventional theses on the radiosity method discuss as to how the form factor is obtained with high efficiency and less errors. For example, Hemi-cube (M. Cohen et al., "The hemi-cube: A radiosity solution for complex environment," Proc. SIGGRAPH'85, 31-40, 1985) and Nusselt Analog (M. Cohen and J. R. Wallance, "Radiosity and Realistic Image Synthesis," Academic Press Professional, Cambridge, Mass. 1933 and A. Doi,"Bidirectional Radiosity Approach for Complex Environments," Denshi Tokyo, IEEE Tokyo Section, No. 32, 93-99, 1933) are known as very famous methods.
Here the Nusselt Analog relating to the present invention will briefly be described. As shown in FIG. 4, when two geometrical elements A.sub.i and A.sub.j are present and A.sub.i is a light source, the center of a unit hemisphere is put to a point X.sub.i in the element A.sub.i. The normal at this point X.sub.i is taken just above the unit hemisphere. Then, the element A.sub.i is projected on the unit hemisphere and its image is mapped onto the bottom surface of the unit hemisphere. The property that the mapped area on the bottom surface of the unit hemisphere becomes equal to the form factor F.sub.ij (exactly speaking, IIF.sub.ij A.sub.i) is employed. Then, by placing a Z buffer, which is often used in hidden-surface processing, on the bottom surface of the unit hemisphere, the V.sub.ij term in Equation 2 is also absorbed. Then, approximation of the form factor will become comparatively easy. The buffer is called an item buffer, because the buffer describes not a Z value but whether the geometrical element is visible.
Much consideration of how spotlight is handled in the radiosity method has not been given. Cohen et al have proposed in the aforementioned theses a model by which the form factor F.sub.ij of spotlight is approximated as follows.
Equation 4! ##EQU4##
In Equation 4, .phi..sub.j represents the angle formed between a line L, which connects the center X.sub.i of the spotlight and a view point X.sub.j on A.sub.j, and the normal vector of A.sub.j. .phi..sub.i represents the angle formed between the directional vector of the spotlight and the line L. V.sub.ij, as with the aforementioned, indicates whether A.sub.j is seen from A.sub.i. The term of cos .sup..alpha..phi..sub.i in Equation 4 corresponds to the aforementioned equation (1) where the intensity-value of the spotlight is attenuated by .alpha.. However, contribution of .THETA. and contribution of .delta. in FIG. 4 are not included in Equation 4.
The Background arts, where the error of the radiosity calculation is reduced and quality is enhanced, are roughly classified into a preprocessing type and a postprocessing type. For the preprocessing type, there is a method where, in radiosity calculation itself, a finite element method is applied to the minimum geometrical element unit of a mesh by using a base function of a linear, degree two, degree three, or higher, not a constant base function. (see R. Troutman and N. Max, "Radiosity Algorithms Using Higher Order Finite Element Methods," Proc. SIGGRAPH'93, 209-212, 1993 and H. Zats, "Galerkin Radiosity: A Higher Order Solution Method for Global Illumination," Proc. SIGGRAPH'93, 213-220, 1993) However, the radiosity calculation using the finite element method is not of practical use, because it takes substantial time and a special process is needed in the shading process.
In the postprocessing type, radiosity is usually calculated on the assumption that a constant base function is employed, and various kinds of interpolation methods are employed instead of flat shading. A most simple method is to average the values of elements (e.g., a sample value at a center point), sampled by a constant base function, by using the value of an adjacent element to obtain an energy value at each vertex. This method is called Nodal averaging. Also, when each geometrical element is a triangle, there is an approach to interpolate energy at an arbitrary point in the triangle element with barycentric coordinates (a kind of bilinear interpolation). Furthermore, an interpolation method using a polynomial of higher degree has been proposed. However, these methods for enhancing quality are limited to the interpolation inside of a minimum geometrical element and has the disadvantage that a result largely depends upon the manner in which meshing is performed. As an approach such as making the boundary between light and shade as clear as possible in the result of radiosity, there is discontinuity meshing (D. F. Lischinski et al, "Discontinuity Meshing for Accurate Radiosity," IEEE Computer Graphics & Applications, 12(6), 25-39, 1992). However, this method explosively increases the number of meshes. Therefore, it is nonrealistic that the geometrical element data, obtained by the method, is processed in a manner that a view point is varied interactively by the Gouraud shading of the hardware.